package org.liaohailong.helloworld.linkedlist;

import java.util.HashMap;
import java.util.Map;

/**
 * Author: liaohailong
 * Date: 2021/5/16
 * Time: 18:07
 * Description:
 **/
public class LLS2 {

    Node last = null;

    // LC 扁平化多级双向链表
    public Node flatten(Node head) {
        if (head == null) return null;

        Node node = head;
        last = head;
        while (node != null) {
            if (node.child != null) {
                Node next = node.next;

                Node child = flatten(node.child);
                node.child = null;

                child.prev = node;
                node.next = child;

                Node temp = last;
                if (next != null) {
                    next.prev = temp;
                    temp.next = next;
                    node = next;
                } else {
                    node = temp;
                }
            } else {
                node = node.next;
            }
            if (node != null) last = node;
        }

        return head;
    }

//    private Node prevNode = new Node();
//
//    // LC 扁平化多级双向链表
//    public Node flatten(Node head) {
//        dfs(head);
//        if (head != null) head.prev = null;
//        return head;
//    }
//
//    public void dfs(Node node) {
//        if (node == null) return;
//
//        Node left = node.child;
//        Node right = node.next;
//
//        prevNode.next = node;
//        node.prev = prevNode;
//        prevNode = node;
//        dfs(left);
//        node.child = null;
//        dfs(right);
//    }


    //        执行用时：
//        1 ms
//                , 在所有 Java 提交中击败了
//        14.65%
//                的用户
//        内存消耗：
//        38.3 MB
//                , 在所有 Java 提交中击败了
//        42.50%
//                的用户
    // LC 复制带随机指针的链表
//    public Node copyRandomList(Node head) {
//        if (head == null) return null;
//
//        // 节点对应下标
//        Map<Node, Integer> node2index = new HashMap<>();
//        // 下标对应random节点
//        Map<Integer, Node> index2random = new HashMap<>();
//        // 结果链表下标对应的节点
//        Map<Integer, Node> index2result = new HashMap<>();
//
//        // 结果链表头部
//        Node p = new Node(head.val);
//        Node n = p;
//
//        // 把链表头部加载进来
//        node2index.put(head, 0);
//        index2random.put(0, head.random);
//        index2result.put(0, p);
//
//        Node node = head.next;
//        int pos = 1;
//        while (node != null) {
//            // 记录原链表下标对应的随机节点
//            index2random.put(pos, node.random);
//
//            // 记录原链表节点对应的下标
//            node2index.put(node, pos);
//
//            // 复制出新链表
//            int val = node.val;
//            n.next = new Node(val);
//            n = n.next;
//            // 记录新链表下标与节点的映射
//            index2result.put(pos, n);
//
//            node = node.next;
//            pos++;
//        }
//
//        // 遍历复制链表，创建随机节点
//        n = p;
//        pos = 0;
//        while (n != null) {
//            Node random = index2random.get(pos);
//            if (random == null) {
//                n.random = null;
//            } else {
//                Integer index = node2index.get(random);
//                n.random = index2result.get(index);
//            }
//            n = n.next;
//            pos++;
//        }
//
//        return p;
//    }

    //    执行用时：
//            0 ms
//, 在所有 Java 提交中击败了
//100.00%
//    的用户
//    内存消耗：
//            38.5 MB
//, 在所有 Java 提交中击败了
//8.60%
//    的用户
    // LC 复制带随机指针的链表
    public Node copyRandomList(Node head) {
        // 旧节点,新节点
        Map<Node, Node> cache = new HashMap<>();

        Node node = head;
        Node cp = null;
        while (node != null) {
            Node cur = new Node(node.val);
            if (cp == null) cp = cur;
            else {
                cp.next = cur;
                cp = cp.next;
            }
            cache.put(node, cur);
            node = node.next;
        }

        node = head;
        while (node != null) {
            Node current = cache.get(node);
            current.random = cache.get(node.random);
            node = node.next;
        }

        return cache.get(head);
    }

//    执行用时：
//            2 ms
//, 在所有 Java 提交中击败了
//9.59%
//    的用户
//    内存消耗：
//            37.9 MB
//, 在所有 Java 提交中击败了
//47.94%
//    的用户
    // LC 旋转链表
//    public ListNode rotateRight(ListNode head, int k) {
//        if (head == null || head.next == null) return head;
//        Stack<ListNode> stack = new Stack<>();
//        int cnt = 0;
//        ListNode node = head;
//        while (node != null) {
//            stack.push(node);
//            cnt++;
//            node = node.next;
//        }
//        k %= cnt;
//
//        if (k == 0) return head;
//
//        ListNode last = stack.peek();
//        ListNode newHead = null;
//        while (k-- > 0) {
//            newHead = stack.pop();
//        }
//
//        stack.peek().next = null;
//        last.next = head;
//        return newHead;
//    }

    // LC 旋转链表
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;

        int n = 1;
        ListNode node = head;
        while (node.next != null) {
            n++;
            node = node.next;
        }

        // 闭环
        node.next = head;

        k %= n;
        if (k == 0) {
            node.next = null;
            return head;
        } else if (k == 1 && n == 2) {
            head.next = null;
            return node;
        }

        node = head;
        // n-k is new head
        // move == 1, node is tail
        int move = n - k;
        while (move-- > 1) {
            node = node.next;
        }

        // node is tail, node.next is head
        ListNode newHead = node.next;
        node.next = null;
        return newHead;
    }


    public static final class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
        public Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public static final class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
